package leetcode_day._2021._202106._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/9 21:45
 * 盈利计划
 * 算法：动态规划
 * 组合题目
 * 只是多了两个要求，之前的背包就是一个数组
 * 而这是两个数组，跟零和一那题差不多
 */
public class _09_879 {

    // 三维 dp 数组，表示前 i 个任务，前 j 个人的情况下，盈利是多少
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length, mod = (int) 1e9 + 7;
        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= len; i++) {
            int m = group[i - 1], p = profit[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= m) dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - m][Math.max(0, k - p)]) % mod;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i <= n; i++) sum = (sum +  dp[len][i][minProfit]) % mod;
        return sum;
    }

    // 二维 dp 数组, 因为这里要求的是至少为 minProfit，而不是最大的，
    // 按照不超过最大的，那么二维长度是最大的数，但这里不知道，所以二维长度为 minProfit
    // 所以 dp[i][j] <= 0 是需要的组合, 这里 k <= 0
    // 而且要从后往前计算，不然会把前面的数据覆盖掉
    public int profitableSchemes_other(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length, mod = (int) 1e9 + 7;
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 0; i < len; i++) {
            int m = group[i], p = profit[i];
            for (int j = n; j >= m; j--) {
                for (int k = minProfit; k >= 0; k--) dp[j][k] = (dp[j][k] + dp[j - m][Math.max(0, k - p)]) % mod;
            }
        }
        return dp[n][minProfit];
    }

}
